package 左哥算法.ch15并查集;

public class UnionFindArray {
    private Integer[] parent;
    private int[] size;
//    private int count;    //需要就封装
    public UnionFindArray(int n) {
        parent = new Integer[n + 1];
        size = new int[n + 1];
//        n=count;
    }

    public int find(int o) {
        if (parent[o] == null || parent[o] == o) {
            return o;
        }
        return parent[o] = find(parent[o]);
    }

    /**
     * @return：如果原本就是同一个集合，返回false，非同一集合返回true
     */
    public boolean union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) return false;
        if (size[pa]<size[pb]){
            pb=pa^pb;
            pa=pa^pb;
            pb=pa^pb;
        }
        parent[pb]=pa;
        size[pa]+=size[pb];
        //--count
        return true;
    }


//    public static void main(String[] args) {
//        UnionFindArray<String> stringUnionFindArray = new UnionFindArray<>(1);
//    }
}
